This invention relates to the lossless coding and decoding of waveform data so as to reduce the required data rate without any alteration of the decoded waveform data, particularly the use of lossless prediction and matrixing methods with particular regard to those using finite precision non-integer arithmetic unaffected by rounding errors and to applications in audio and image waveform coding and decoding.
The data rate occupied by audio or other waveform data in digital PCM (pulse code modulation) form is often too high for the transmission or storage medium used to convey waveforms. Methods of reducing waveform data rate are known in the prior art and may be classified into two types, lossy and lossless coding. Lossy coding discards or alters the waveform data in a way which is small in relation to the requirement of how the data is used, whereas lossless coding reduces the data rate by eliminating signal redundancies in coded form, but in a way that allows the exact original data to be recovered by a decoding process.
Such lossless coding methods based on the use of predictors are known in the prior art and are described for example in C. Cellier, P. Chenes and M. Rossi, xe2x80x9cLossless Audio Bit Rate Reductionxe2x80x9d, Audio Engineering Society UK xe2x80x9cManaging The Bit Budgetxe2x80x9d Conference proceedings, May 16-17, 1994, pp.107-122, in R. C. Gonzales and R. E. Woods, xe2x80x9cDigital Image Processingxe2x80x9d, Addison Wesley, Reading Mass., 1992 Chapter 6, esp. section 6.4.3 pp.358-362 and in M. Rabbani and P. W. Jones, xe2x80x9cDigital Image Compression Techniquesxe2x80x9d, SPIE Press, Bellingham, Wash. 1991.
PCM signals may be considered as integer- valued time series signals, where the integer is a multiple of the value of the least significant digit. The basic concept in prior art systems is to encode the integer PCM signal via a prediction filter where the quantizer comprises a rounding operation to the nearest integer, transmitting the quantized difference (termed here the prediction-encoded signal) between the actual signal and predicted signal derived from the output of the quantizer, and then to transmit this encoded data efficiently by means of Huffman coding or by transmitting the number of zero MSBs (most significant bits) once only for a block of words or similar techniques of reducing the wordlengths of the individual samples of the encoded waveform. In such prior art systems, lossless decoding is done by using Huffman or other appropriate decoding to restore the wordlength of the encoded signal, and then to pass the encoded data into an identical predictor filter to that used in encoding, to add the result to the encoded signal, and then to restore the original integer valued signal by means of a second rounding quantization operation. The rounding operations may be omitted if the prediction filters have only integer coefficients.
However, in many applications, prior art methods of lossless encoding and decoding of waveform data have considerable practical problems. This is particularly the case with high quality PCM audio data, especially when transmitted through media with limitations on the peak data rate at which data can be transferred, such as compact disc players or digital tape recorders.
By high quality audio we mean signals which in PCM form will typically require 16 or more bits, perhaps as many as 20 or 24 bits, for accurate representation of the digital words, and sampling rates of 44.1 kHz or higher.
Lossless compression of audio data is especially useful when in addition the sampling rate is a high figure such as 96 kHz. Such high sampling rates are coming into use for the case where an extended audio bandwidth is required for premium quality of reproduction. When it is desired in addition to convey multichannel stereo or surround sound, one may need to convey to the user perhaps 5 or 6 channels of audio at a 96 kHz sampling rate with around 20 bit resolution, and the resulting data rates of around 11.5 Mbit/second are difficult to convey with adequate playing time via existing storage media such as high-density compact disc or optical storage media.
In any case, lossless coding and decoding of such high quality audio data allows the effective capacity of storage media such as hard disc in computer-based audio processing systems to be increased, as well as increasing the effective storage capacity of storage media such as compact disc, digital tape media and the like. In such applications, it is desirable that especially the decoding algorithms should be relatively simple to implement, because the number of players may well outnumber the number of recorders by a large factor, especially for compact disc type releases of audio music programme material. There is also a requirement that the encoding and decoding algorithms be transportable to many different digital signal processing platforms without too much difficulty of engineering implementation, since encoded recordings produced by any one of many record companies or other organisations would be expected to play back on players of many different users made by many different manufacturers.
In the prior art, the simplest and in audio most widely used form of lossless waveform coding used is an integer prediction technique. This comprises transmitting not the PCM audio signal itself, but the difference between successive samples plus an initial sample, from which the original signal can be reconstructed by recovering each sample by adding the difference sample to the previously recovered sample. For typical audio signals, the difference signal will have lower energy than the original signal. A known and widely used prior-art extension of this integer prediction technique may instead transmit second or third differences of the signal along with two or three initial samples of the PCM signal. Using the symbol zxe2x88x921  to indicate a delay by one sample, this method transmits the result of passing the signal through an encoding filter of the form (1xe2x88x92zxe2x88x921)n or n=0, 1, 2 or 3. The original signal can be recovered from the data by an inverse summation process. The value of n may be chosen adaptively, block by block of audio waveform samples, so as to minimise the energy of the transmitted signal at each moment, since low-energy waveform data can be transmitted at a lower data rate than higher-energy waveform data.
Integer-coefficient predictors are found to reduce the average data rate and content of most audio signals, but can actually increase the peak data rate required for transmission. This makes such predictors unsuitable for coping with media having peak data read or write rate limitations. Also, the optimal prediction filter for minimising data rate is well known, see J. I. Makhoul, xe2x80x9cLinear Prediction: A Tutorial Reviewxe2x80x9d, Proc. IEEE, vol. 63, pp. 561-580 (April 1975), to be one such that the frequency response of the difference between actual and predicted signal is approximately inverse to the spectrum of the waveform signal to be encoded, and for many signals, integer-coefficient prediction filters only very poorly approximate this requirement. Thus integer filters give a suboptimum average data rate as well. For encoding audio signals, these inefficiencies of integer predictors particularly affect such signals as speech sibilants, popular music with high treble energy, cymbal waveforms and suchlike.
Predictors involving non-integer coefficients can encode waveforms with much better reductions of both peak and average data rates, but unfortunately, these have the problem that an ideal implementation requires the use of infinite-precision arithmetic, which is not possible. In practice, one uses prediction filters incorporating rounding errors in their arithmetic, and in such a case, it is essential for lossless coding that the rounding errors in the predictors be absolutely identical in the encoder and the decoder. This requirement of identical rounding errors makes it very difficult to transport a decoding or encoding algorithm between different signal processing hardware, where slight differences in rounding errors are encountered. In applications where a wide variety of equipment designs may be used to encode or decode signals, it is practically necessary to use algorithms that are transportable between different DSP (Digital signal processing) platforms which may not have identical rounding errors. Also, the need to control arithmetic rounding errors in predictors to be absolutely identical makes it very difficult to design alternative prediction filter architectures for particular applications when it is known that different encoders and decoders must work with each other.
In addition, existing non-integer lossless prediction algorithms add a quantization noise to the encoded signal that has a spectrum that is inverse to the frequency response of the difference between actual and predicted signal. For low-level waveform signals, the amplitude of this added quantization noise can dominate in the encoded signal, increasing its average amplitude and hence the encoded data rate unnecessarily.
Existing lossless prediction methods in addition only encode and decode single channels of waveform data separately from each other. In many applications, including stereo and multichannel audio, one wishes to encode two or more related waveform signals which quite often have a high degree of correlation. One wishes to have lossless coding which can take advantage of the redundancy due to such correlations to reduce the data rate further.
This invention describes modified methods of prediction and matrixing based on non-integer finite precision prediction filter coefficients, and on the additional optional use of integer-coefficient or finite-precision non-integer-coefficient noise shaping filtering around the integer rounding operation quantizer.
According to the invention in a first aspect, an encoding filter predictor arrangement for integer-valued waveform signal data comprises an integer-valued input waveform signal, a summing node followed by a rounding-operation quantizer giving as output a prediction-encoded signal, said summing node being fed from the input waveform signal by a direct path from the input signal and by a filter A having a delay of at least one sample, and fed also recursively from the output of said quantizer via a second filter B having a delay of at least one sample. The inverse decoder comprises an identical arrangement save that the input signal is now the prediction encoded signal, the output of the quantizer rounding operation is the recovered original input integer-valued signal to the encoder, and the filters A and B are interchanged, and that the quantizer in the decoder has performance equivalent to the encoder quantizer both preceded and followed by a polarity inversion.
In preferred implementations of the invention in its first aspect, the filters A and B are FIR (finite impulse response) filters.
In further preferred implementations of the invention in its first aspect, said FIR filters A and B and have finite precision non-integer coefficients.
It is further preferred that said filters are implemented either without rounding error or only with rounding errors that do not affect the value of the output of said quantizer.
By finite precision non-integer coefficients, we mean that all coefficients can be impressed as rational numbers with an integer common denominator d such that the filter arithmetic can be performed without ambiguous rounding errors.
And by non-integer we mean that at least one such coefficient is not an integer.
In all aspects of this invention, moving summing nodes handling signals divisible by G quantized to a step size G from before to after an quantizer with step size G or vice-versa does not change the nature of the invention, but is merely an obvious variant of implementation. Thus in the invention in its first aspect, any summation before the quantizer involving an integer signal input, such as the direct path from the input to the summing node, may instead be added at a summing node after the quantizer but before the output. In addition, identical noise shaping may be employed around the encoding and decoding quantizers. It is preferred that either the noise shapers have finite precision arithmetic FIR filtering using the outer-form noise shaping architecture whereby the difference between the input and the output of the noise-shaped quantizer system is fed via a FIR (finite impulse response) filter D with finite precision non-integer coefficients and having a delay of at least one sample to the input of the quantizer, or that the noise shaping filters have integer arithmetic filtering.
A survey of noise shaping methods and architectures may be found in section 1 of: M. A. Gerzon, P. G. Craven, J. R. Stuart and R. J. Wilson, xe2x80x9cPsychoacoustic Noise Shaped Improvements in CD and Other Linear Digital Mediaxe2x80x9d, Preprint 3501 of the 94th Audio Engineering Society Convention, Berlin, (Mar. 16-19, 1993). As well as describing many different forms of noise shaping topology having equivalent performance, this reference describes methods of rearranging filters with integer and non-integer coefficients around quantizers that may advantageously be applied to implementing the present invention.
Such encoding and decoding filter predictor arrangements, either with or without noise shaping, may be implemented using finite-precision fixed point arithmetic, and so may be implemented without any effect from rounding errors in the filtering operations. As a result, they are capable of being transported between different fixed point DSP implementations and platforms. The only rounding operation that needs to be implemented is the one in the quantizer rounding operation. Although as a matter of practical convenience, the finite precision coefficients will often be fractions having only a restricted number of fractional binary digits, it will be understood that by finite precision non-integer coefficients, we mean coefficients that have fractional parts defined as rational ratios of two integers, since finite precision can be defined in integer arithmetic to any base, not just to base 2.
In the invention according to the first aspect, the encoding filter predictor arrangement reducing average wordlength differs from the prior art in arranging that not all the prediction filtering is done recursively around the rounding quantizer, but ensuring that the numerator of the encoding filter is implemented prior to the quantizer, and only its denominator is implemented recursively around the quantizer. The prediction decoding arrangement restoring the increased original wordlength also differs from the prior art in arranging that not all the rounding quantization is done subsequent to the filtering, but is done in a recursive loop for the denominator of the decoding filter, and is preceded only by the numerator of the decoding filter.
Also differing from the prior art in lossless encoding and decoding is the use of noise shaping around the encoder and the decoder quantizer. The use of such noise shaping allows improved control of either the data rate of encoded signals during low-level waveform passages or the recovery properties in decoding from data errors in transmission.
In many practical implementations of the invention, the encoding filter predictor arrangement may be applied to blocks of waveform samples, the length L of such a block often being of order of magnitude 576 samples. When encoding such a block of samples, one typically will choose a predictor filter arrangement that approximately minimises the average or peak encoded signal energy within the block, and transmit the filter coefficients used for encoding as additional data. The decoder will load the same filter coefficients into the inverse decoding filter arrangement. In order that the decoding filter arrangement reconstruct the waveform accurately, it is usually necessary that the initial filter state variables at the start of the block be identical in the decoding and encoding filter, and it is also usually necessary to transmit such state variables to xe2x80x9cinitialisexe2x80x9d the state variables in the decoding filter at the start of a block or at the start of a sequence of blocks at which the filter coefficients have been changed. In practice, suitable state variables for a filter with n""th order denominator and numerator are the first n input samples and the first n output samples of the encoding filter at the start of the block. These are used respectively as the first n output samples and the first n input samples of the decoding filter in the block.
Where noise shaping filters are used, the state variables of the noise shaping filter in decoding also usually must be correctly initialised, and transmitted for use by the decoder.
It is also clear that a succession of cascaded encoding filter predictor arrangements at least one of which is according to the invention may be used for lossless encoding, and that the inverse lossless decoding arrangement is a cascade in reverse order of inverse decoding filter predictor arrangements at least one of which is according to the invention.
The invention is applicable to PCM signals in their most general sense, i.e. signals represented by integer numbers representing the value of a waveform on a relatively large number of sampling instants or points. Although practical implementation will normally use binary digital representations of the numbers, representations to any other numerical base may be used. Any references to least or most significant bits may be generalised in such non-binary representations to least or most significant digits.
According to the invention in a second aspect, invertible transformation means for converting input integer-valued PCM waveform data to output integer-valued PCM waveform data are provided, comprising:
an input for said input integer-valued PCM waveform data,
an output for said output integer-valued PCM waveform data,
a summing node,
a quantizer rounding operation rounding to near or nearest integer values,
a first filter means A each term of which incorporates delay, and
a second filter means B each term of which incorporates delay, wherein
the input feeds said summing node directly,
the input feeds said summing node via the filter A,
the summing node feeds the quantizer,
the quantizer feeds the output, and
the output feeds the summing node via the filter B.
According to the invention in a third aspect, invertible transformation means for converting input integer-valued PCM waveform data to output integer-valued PCM waveform data are provided, comprising:
an input for said input integer-valued PCM waveform data,
an output for said output integer-valued PCM waveform data,
a summing node,
a differencing node,
a quantizer rounding operation rounding to near or nearest integer values,
a first filter means A each term of which incorporates delay,
a second filter means B each term of which incorporates delay, and
a first and a second invertible integer waveform transformation arrangement having no input/output delay, wherein
the input feeds said summing node via said first invertible integer waveform transformation arrangement,
the input feeds said differencing node via the filter A,
the output feeds said differencing node via the filter B,
the differencing node feeds the quantizer,
the quantizer feeds the summing node, and
the summing node feeds said output via the second invertible integer waveform transformation arrangement.
By an invertible integer waveform transformation arrangement we mean any method of transforming one integer-valued signal to another such that there exists an inverse transformation arrangement taking integer-valued signals to integer-valued signal that restores the original integer-value signal from the transformed integer-valued signal. By saying it has no input/output delay, we mean that it has a causal implementation and the inverse has a causal implementation such that the two cascaded have no overall delay. The lossless encoding and decoding filter arrangements of the present invention are themselves examples of an invertible integer waveform transformation arrangement having no input/output delay, and several other examples of such arrangements are given in this description. Such arrangements may be xe2x80x9ctrivialxe2x80x9d, i.e. have output equal to for example the input or minus the input.
The inverse transformation means of the invention according to its second or third aspects is described is the body of the description with reference to FIGS. 6b or 15d below. It is another arrangement of a similar kind, but with filters A and B interchanged and first and second invertible integer waveform transformation arrangements both inverted and interchanged. If one example of the invention in its second or third aspects are used for encoding waveform data, the inverse arrangement is used for decoding waveform data, or vice-versa.
In a fourth aspect of the invention, the quantization process within the encoding and decoding filter has a smaller fractional step size than the output quantization in order to reduce the overall quantization noise added to the prediction-encoded signal. A number n of reduced step-size filter stages may be cascaded to produce complicated encoding and decoding filters without undue build up of transmitted quantization noise that may degrade the data rate of the prediction-encoded signal.
According to the invention in a fourth aspect, invertible transformation means for converting input integer-valued PCM waveform data to output integer-valued PCM waveform data are provided, comprising:
an input for said input integer-valued PCM waveform data,
an output for said output integer-valued PCM waveform data,
a first to an n""th quantizing filter stages,
an integer quantizer rounding operation rounding to near or nearest integer values, wherein
the input feeds said first quantizing filter stage,
the i""th quantizing filter stage feeds the i+1""th quantizing filter stage for all i=1 to nxe2x88x921,
the n""th quantizing filter stage feeds the integer quantizer rounding operation,
the integer quantizer rounding operation feeds the output, wherein
each quantizer filter stage i incorporates a fractional-step quantizer rounding operation with step size 1/G1 an integer divisor G1 of unity such that the output of that stage is quantized to that step size
each quantizer filter stage i incorporates a feedforward filter Ai having a delay of at least one sample prior to said fractional-step quantizer fed by the input to the quantizer filter stage and the filter output being summed with said input at a summing node, and
each quantizer filter stage i incorporates a feedback filter Bi having a delay of at least one sample prior to said fractional-step quantizer fed by the output of the quantizer filter stage and the filter output being differenced with the output of said feedforward filter Ai at a summing node.
In preferred implementations of the invention in its second, third or fourth aspect, the filters A and B or Ai and Bi are FIR (finite impulse response) filters each term of which incorporates delay.
In preferred implementations of the invention in its second, third or fourth aspect, said FIR filters A and B or Ai and Bi have coefficients all of which have finite fractional precision.
It is further preferred that said filters are implemented either without rounding error or only with rounding errors that do not affect the value of the output of said quantizer.
In the invention according to its second, third or fourth aspect, the quantizers may optionally incorporate noise shaping. It is preferred that either the coefficients of the noise shaping filter are integer or the noise shaper is outer-form with FIR filter having coefficients of finite precision.
In implementations of the invention according to its second third or fourth aspect, wherever a summing node before a quantizer is fed with a signal whose quantization step size is a equal to or an integer multiple of the quantizer step size, the invention may equivalently be implemented with the signal being added at a summing node immediately after the quantizer, or vice-versa.
In the invention according to its fourth aspect, the arrangement of cascaded quantizing filter stages followed by an integer quantizer may be used either for lossless encoding or for lossless decoding. Also according to the invention, an inverse arrangement using as a feedback sidechain around the integer quantizer the cascaded filters with all undelayed signal paths omitted and with direct feeds from the input being via all the delay filters Ai and Bi, described herein with reference to FIGS. 16 and 17 below, is used for decoding or encoding respectively and is also according to an aspect of the invention.
Preferably, according to the invention in the above aspects, the filter arrangements used for encoding and the inverse filter arrangements used for decoding will be causal and stable, so that the filter outputs do not increase in magnitude unduly.
It is necessary for stability of encoding and decoding that the encoding and decoding filters be of minimum phase form, i.e. that they and their inverses (ignoring quantization) be stable according to well known stability criteria, such as the filter poles and zeros all being within or on the unit complex circle. See any standard textbook on the theory of digital filtering, for example A. Antoniou, xe2x80x9cDigital Filters Analysis, Design and Applicationsxe2x80x9d, 2nd. edition, McGraw-Hill Inc., New York, 1993.
However, although highly preferable, it is not essential that the decoding filter be stable, since the lossless inverse nature of the decoding will ensure exact recovery of the input. However, if an encoding filter arrangement is used that is not minimum phase, in general the wordlength will not be reduced by as much by the encoding arrangement as by suitable encoding filter arrangements that are minimum phase. Also, the use of a non-minimum phase encoding filter arrangement will result in a decoding arrangement that is poor at recovering from data errors in transmission.
The invention may also be applied to lossless encoding and lossless decoding of related multichannel waveform signals in PCM form, wherein the cascaded stages of encoding may include lossless matrix encoding stages and the cascaded stages of decoding may include lossless matrix decoding stages.
Such lossless matrix encoding stages again, according to the invention, may use non-integer coefficients of finite precision and comprise individual stages of processing wherein only one channel is modified in each stage, said channel having as output a quantization or rounding to the nearest integer of a linear combination of the input channels to that stage, with the coefficient of the altered channel being unity. The inverse lossless matrix decoding stage in the inverse lossless decoder comprises a similar arrangement except that the signs of the coefficients of all the unaltered channels are reversed, and where the quantizer in the decoder has the same effect as the quantizer in the original encoder. The lossless encoding and decoding stages may also incorporate an overall polarity inversion applied to any subset of the n channels.
A cascade of lossless matrix encoding stages applied to n channels is here termed an nxc3x97n matrix quantizer, and the inverse cascade of lossless matrix decoding stages that reverses the effect of such an nxc3x97n matrix quantizer applied to n channels is here termed the inverse nxc3x97n matrix quantizer. Typically, such nxc3x97n matrix quantizers are used in encoding n-channel PCM waveform data to reduce the data rate by altering input channels so that the output channel signal are linear combinations of channels having lower energy and total encoded data rate.
The invention according to a fifth aspect may be applied to related multichannel waveform signals.
According to the invention in a fifth aspect, invertible transformation means for converting an input integer-valued PCM n-channel waveform data to output integer-valued PCM n-channel waveform data are provided, comprising:
an n-channel input for said input integer-valued PCM n-channel waveform data,
an n-channel output for said output integer-valued PCM n-channel waveform data,
an n-channel summing node,
an n-channel differencing node,
an n-channel quantizer rounding operation rounding to near or nearest integer values,
a first nxc3x97n matrix filter means A each term of which incorporates delay,
a second nxc3x97n matrix filter means B each term of which incorporates delay, and
a first and a second nxc3x97n matrix quantizer as defined herein, wherein
the n-channel input feeds said summing node via said first nxc3x97n matrix quantizer,
the n-channel input feeds said differencing node via the nxc3x97n matrix filter A,
the n-channel output feeds said differencing node via the nxc3x97n matrix filter B,
the n-channel differencing node feeds the n-channel quantizer,
the n-channel quantizer feeds the n-channel summing node, and
the n-channel summing node feeds said n-channel output via the second nxc3x97n matrix quantizer.
In preferred implementations of the invention in its fifth aspect, said nxc3x97n matrix filter means A and B are matrix FIR filters.
In preferred implementations of the invention in its fifth aspect, said nxc3x97n matrix FIR filter means A and B have coefficients all of which have finite fractional precision.
It is further preferred that said filter means are implemented either without rounding error or only with rounding errors that do not affect the value of the output of said quantizer.
The inverse transformation means of the invention according to its fifth aspects is described is the body of the description with reference to FIGS. 24d below. It is another arrangement of a similar kind, but with the matrix filters A and B interchanged and first and second nxc3x97n matrix quantizers both inverted and interchanged. If one example of the invention in its second or third aspects are used for encoding waveform data, the inverse arrangement is used for decoding waveform data, or vice-versa.
The invention according to any of the five above aspects may be applied to related multichannel waveform signals, wherein the FIR filters A and B or Ai and Bi in the encoding and inverse decoding filters are matrix filters wherein each channel input feeds each channel output by an FIR filter with finite precision coefficients, and the noise shaping filter may also be a matrix filter. In the matrix case, the stability criterion is that all the poles and zeros of the filter defined by the determinant of the matrices lie within or on the unit circle.
As will be described in more detail below, in the case where the FIR filter A or Ai in the encoder is xe2x80x9cleakyxe2x80x9d, i.e. is strictly stable and has no zeros on the unit circle, then it may not be necessary to transmit initialisation state variables from the encoder to the decoder, since in that case, the state variables will, after a sufficient elapse of time with actual input signals, eventually attain the same values in the decoder as in the encoder, and from that point onwards the decoding will become lossless.
The invention according to any aspect may also be applied to waveform signals defined on discrete arrays having more than one dimension, such as two-dimensional image waveforms. In this case the filters A and B or Ai and Bi and the noise shaper are two- or more-dimensional FIR filters, each term of which has at least one sample delay in at least one of the array axis directions. The criteria ensuring stability of filters on arrays in more than one dimension is more complex than the one-dimensional theory, but suitable methods of determining stability of such filters may be found for example in R. R. Read, J. L. Shanks and S. Treitel, xe2x80x9cTwo Dimensional Recursive Filteringxe2x80x9d, in ed. T. S. Huang, xe2x80x9cPicture Processing and Digital Filtering, 2nd Editionxe2x80x9d, Topics in Applied Physics, vol. 6, Springer Verlag, Berlin, 1979 pp. 131-176.
All above aspects of the invention may be used and preferably are used with an associated entropy or Huffman or similar encoding or decoding arrangement. The use of such entropy or Huffman or similar encoding at the output of a PCM waveform data encoding arrangement according to the above aspects of the invention provides a lower data rate for the encoded signal, and it is also necessary for the associated decoder to precede the decoding filter arrangement according to any of the above aspects of the invention by an inverse entropy or Huffman or similar decoding. The invention may also be applied to input signals having any uniform quantization step size G by regarding the step size as being the unit integer for the purposes of implementing the invention. In particular, the input signal to an encoder may be pre-processed to remove DC components and to normalise the gain so that the step size becomes or may be regarded as unity, and the decoder can be followed by an inverse process of multiplying by the original step size G and re-inserting the DC component.
In transmitting PCM signals, it may be desired to handle PCM waveform signals of different wordlengths or precision in a common manner. This may be done in the PCM representation by adding to shorter word length additional least significant digits having a constant unvarying form to shorter word length to bring them up to a common longer word length. Data rate savings in transmitting such signals may be obtained not only by reducing the transmitted integer signal energy, but by in addition detecting in longer wordlength PCM signal whether such constant least significant digits are present for extended sequences of samples, and if so to transmit the digital words in encoded form without the least significant digits, transmitting these least significant digits just once separately during a sequence, and by adding these least significant digits back in the decoder. By this means a single common format may be used to transmit a wide variety of word lengths while allowing data rates automatically to adjust according to the word length.
In particular, an encoder and a decoder may be used in which the wordlength and word precision is adaptive moment by moment for successive blocks of waveform samples, using a possibly different wordlength in each block.
While this allows lossless encoding and decoding of signals of any fixed wordlength, it also permits the encoders and decoders of the present invention to be used with a lossy encoding system as well.
This is done, according to the invention in a sixth aspect, by preceding a lossless encoder adaptive to wordlength and word precision by an adaptive rounding algorithm which block by block of waveform samples rounds or quantizes the waveform data to a reduced precision and incorporates adaptive noise shaping around the quantizer, such that the energy and spectral form of the noise shaped quantization error thus introduced lies below acceptable perceptual thresholds in the presence of the PCM waveform signal at that part of the waveform data. A subsequent associated lossless transmission system adaptive to wordlength and word precision then transmits the modified waveform data without any further loss.
This allows lossless decoding systems adaptive to wordlength and word precision to be used also for lossy transmission of signals according to perceptual criteria where a reduced data rate is required, without requiring any special features in the decoder not already present for lossless decoding purposes. Because the initial perceptual lossy adaptive noise shaped quantization of the waveform signal precedes the encoder, the system is still handling the resulting signal in a lossless form in an efficient manner to reduce data rate as much as possible.
In the invention in its sixth aspect, advantages are obtained over the known prior lossy coding art. In particular, advantages include the following:
A single encoding and decoding strategy and system may be used to handle lossless and lossy encoding, requiring only a single common decoding algorithm for both.
Additionally, for low signal levels, the lossy coding will revert to being lossless since the encoded data rate in quiet passages will be sufficiently low as to require no further discarding of data. Unlike other lossy systems, this will preserve the integrity of quiet passages.
In addition, when lossy encoders according to the invention in its sixth aspect are cascaded, the degree of degradation of the original waveform will not continue to degrade to an indefinite degree (as is the case with conventional perceptual encoders), but rather the degree of degradation will be strictly limited to that caused by the discrete and finite number of degrees of loss of numerical precision that may be achieved. As a result, very large numbers of lossy encode/decode systems according to the invention in its sixth aspect may be cascaded indefinitely without results becoming unacceptable.
Moreover, once lossy coding has been used once according to the invention in its sixth aspect, all subsequent lossless coding systems adaptive to wordlength and word precision according to the invention will continue automatically to transmit signals at the reduced data rate, whereas with conventional perceptual lossy encoding, the decoded signal does not compress efficiently in data rate during any subsequent lossless encoding and decoding operations.
It is obvious that cascading lossless encoding algorithms for integer-valued waveforms will result in more complex composite lossless encoding algorithms whose effect may be undone by an reversed order cascade of inverse lossless decoding algorithms. Therefore the invention includes cascaded or composite encoders or decoders incorporating component encoders or decoders according to the invention in any of its aspects.
Additionally, implementation of the invention may be made rearranging, combining or splitting component subalgorithms in ways evident to those skilled in the art and also on the basis of methods described and referred to herein. In particular, signals divisible by G having a quantization step size G may equivalently be added before or after a quantizer with step size G with equivalent results, and cascaded subalgorithms may be replaced by single subalgorithms known to be of identical performance, or vice-versa. Polarity inversions may be added or removed in ways evident to one skilled in the art, for example changing summing to differencing nodes, provided that the overall functionality remains unchanged. Other re-arrangements of the kind described in section 1 of the above-cited Gerzon, Craven, Stuart, Wilson reference may also be applied to the present invention.